{
 "cells": [
  {
   "attachments": {},
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-Nearest Neighbors\n",
    "\n",
    "\n",
    "K-Nearest Neighbors (KNN) is a non-parametric supervised learning algorithm, suitable for both classification and regression tasks.\n",
    "\n",
    "In classification, KNN aims to identify the nearest points by measuring their similarity, often through distance metrics. New labels are assigned through a majority vote, considering the most frequent labels among the neighboring points.\n",
    "\n",
    "In Fully Homomorphic Encryption (FHE), classification with KNN poses significant computational challenges due to the distance calculations and the sorting algorithms, which is currently a non-stable algorithm (i.e., does not consider the order of the elements). Therefore, it is recommended to use it on small datasets (up to dozens of examples) with strong quantization (n_bits <= 4).\n",
    "\n",
    "This tutorial focuses exclusively on the KNN classifier and compares the performance of Concrete KNN with its scikit-learn counterpart on a small data-set."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Import libraries\n",
    "\n",
    "First, import the required packages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import time\n",
    "\n",
    "import pandas as pd\n",
    "from sklearn.datasets import make_classification\n",
    "from sklearn.metrics import accuracy_score\n",
    "from sklearn.model_selection import train_test_split\n",
    "\n",
    "from concrete.ml.sklearn import KNeighborsClassifier as ConcreteKNeighborsClassifier"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Data-set generation"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "X, y = make_classification(\n",
    "    n_samples=15, n_features=3, n_informative=3, n_redundant=0, n_classes=2, n_clusters_per_class=1\n",
    ")\n",
    "# Split the data-set into a train and testing sets\n",
    "X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.5, random_state=42)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Model instantiation\n",
    "\n",
    "The novel aspect introduced by Concret ML for KNN model is the hyperparameter `n_bits`, which represents the precision for quantizing input data. This quantization step is essential after the training phase, since FHE exclusively operates over integers."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "n_neighbors = 3\n",
    "\n",
    "concrete_knn = ConcreteKNeighborsClassifier(n_bits=3, n_neighbors=n_neighbors)\n",
    "\n",
    "# Fit both the Concrete ML and its equivalent float estimator on clear data\n",
    "concrete_knn, sklearn_model = concrete_knn.fit_benchmark(X_train, y_train)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Compile the model\n",
    "\n",
    "\n",
    "The compilation step aims to:\n",
    "- convert the quantized model to its FHE equivalent\n",
    "- create an executable operation graph\n",
    "- check the operation graph's compatibility with FHE\n",
    "- compute the maximum bit-width needed for model execution\n",
    "- determine cryptographic parameters necessary for generating secret keys and evaluation keys"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Compilation time: 1.90 seconds\n"
     ]
    }
   ],
   "source": [
    "time_begin = time.time()\n",
    "circuit = concrete_knn.compile(X)\n",
    "print(f\"Compilation time: {time.time() - time_begin:.2f} seconds\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Maximum bit-width reached in the circuit: 8\n"
     ]
    }
   ],
   "source": [
    "print(f\"Maximum bit-width reached in the circuit: {circuit.graph.maximum_integer_bit_width()}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Key generation\n",
    "\n",
    "The circuit generated by the compiler is used to generate a set of keys:\n",
    " - a _Secret key_ , held exclusively by the user and used for both encryption and decryption process\n",
    "\n",
    "- an _Evaluation Key_, publicly accessible without compromising the security of the scheme, and used to evaluate the circuit on encrypted data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Key generation time: 29.11 seconds"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n"
     ]
    }
   ],
   "source": [
    "# For circuits exceeding 8-bits, the key generation process might take up to an hour\n",
    "time_begin = time.time()\n",
    "circuit.client.keygen()\n",
    "print(f\"Key generation time: {time.time() - time_begin:.2f} seconds\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Inference with Concrete ML:\n",
    "\n",
    "In Concrete ML, there are 3 ways to run the inference:\n",
    "\n",
    "a. __Clear__: inference on non-encrypted quantized data, without any FHE execution \n",
    "\n",
    "b. __Simulation__: inference on non-encrypted quantized data, while simulating all FHE operations, failure probabilities and crypto-parameters. This mode of inference is recommended in the development phase. For further information, please consult [this documentation section](../explanations/compilation.md#fhe-simulation)\n",
    "\n",
    "c. __Execution in FHE__: inference on encrypted data, using actual FHE execution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "FHE inference execution time: 22.42s per sample\n"
     ]
    }
   ],
   "source": [
    "# a- Clear inference\n",
    "pred_cml_clear = concrete_knn.predict(X_test, fhe=\"disable\")\n",
    "score_cml_clear = accuracy_score(y_test, pred_cml_clear)\n",
    "\n",
    "# b- FHE simulation inference\n",
    "pred_cml_simulate = concrete_knn.predict(X_test, fhe=\"simulate\")\n",
    "score_cml_simulate = accuracy_score(y_test, pred_cml_simulate)\n",
    "\n",
    "# c- FHE inference\n",
    "time_begin = time.time()\n",
    "pred_cml_fhe = concrete_knn.predict(X_test, fhe=\"execute\")\n",
    "print(f\"FHE inference execution time: {(time.time() - time_begin) / len(X_test):.2f}s per sample\")\n",
    "score_cml_fhe = accuracy_score(y_test, pred_cml_fhe)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "# scikit-learn inference\n",
    "predict_sklearn = sklearn_model.predict(X_test)\n",
    "score_sklearn = accuracy_score(y_test, predict_sklearn)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Sckit-learn accuracy: 50.00%\n",
      "Concrete ML (clear) accuracy: 37.50%\n",
      "Concrete ML (FHE simulation) accuracy: 37.50%\n",
      "Concrete ML FHE accuracy: 37.50%\n"
     ]
    }
   ],
   "source": [
    "print(f\"Sckit-learn accuracy: {score_sklearn:.2%}\")\n",
    "print(f\"Concrete ML (clear) accuracy: {score_cml_clear:.2%}\")\n",
    "print(f\"Concrete ML (FHE simulation) accuracy: {score_cml_simulate:.2%}\")\n",
    "print(f\"Concrete ML FHE accuracy: {score_cml_fhe:.2%}\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Predictions in FHE can be time-consuming due to the costly FHE operations. During the development phase, using the simulation mode  offers an efficient and quick way to gauge the model's performance. Especially as it produces similar results."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Concrete KNN vs. scikit-learn KNN\n",
    "\n",
    "Let's compare the top-k labels returned by Concrete and scikit-learn's KNN in the table below, highlighting mismatched predictions."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Retieve topk labels for the scikit-learn model\n",
    "distance, topk_args = sklearn_model.kneighbors(X_test)\n",
    "topk_labels_sk = y_train[topk_args]\n",
    "\n",
    "# Retieve topk labels for the concrete model\n",
    "# `get_topk_labels` method is like `predict` method, but instead of returning the most common labels\n",
    "#  it provides the top K labels.\n",
    "topk_labels_cml = concrete_knn.get_topk_labels(X_test, fhe=\"simulate\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/html": [
       "<style type=\"text/css\">\n",
       "#T_9d3c2_row2_col0, #T_9d3c2_row2_col1, #T_9d3c2_row2_col2, #T_9d3c2_row2_col3, #T_9d3c2_row2_col4, #T_9d3c2_row2_col5 {\n",
       "  background-color: yellow;\n",
       "}\n",
       "</style>\n",
       "<table id=\"T_9d3c2\">\n",
       "  <thead>\n",
       "    <tr>\n",
       "      <th class=\"blank level0\" >&nbsp;</th>\n",
       "      <th id=\"T_9d3c2_level0_col0\" class=\"col_heading level0 col0\" >Distance</th>\n",
       "      <th id=\"T_9d3c2_level0_col1\" class=\"col_heading level0 col1\" >Top3 (scikit-learn)</th>\n",
       "      <th id=\"T_9d3c2_level0_col2\" class=\"col_heading level0 col2\" >Majority vote (scikit-learn)</th>\n",
       "      <th id=\"T_9d3c2_level0_col3\" class=\"col_heading level0 col3\" >Top3 (Concrete ML)</th>\n",
       "      <th id=\"T_9d3c2_level0_col4\" class=\"col_heading level0 col4\" >Majority vote (Concrete ML)</th>\n",
       "      <th id=\"T_9d3c2_level0_col5\" class=\"col_heading level0 col5\" >Ground truth</th>\n",
       "    </tr>\n",
       "  </thead>\n",
       "  <tbody>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row0\" class=\"row_heading level0 row0\" >0</th>\n",
       "      <td id=\"T_9d3c2_row0_col0\" class=\"data row0 col0\" >0.620442</td>\n",
       "      <td id=\"T_9d3c2_row0_col1\" class=\"data row0 col1\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row0_col2\" class=\"data row0 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row0_col3\" class=\"data row0 col3\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row0_col4\" class=\"data row0 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row0_col5\" class=\"data row0 col5\" >0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row1\" class=\"row_heading level0 row1\" >1</th>\n",
       "      <td id=\"T_9d3c2_row1_col0\" class=\"data row1 col0\" >1.098326</td>\n",
       "      <td id=\"T_9d3c2_row1_col1\" class=\"data row1 col1\" >[0, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row1_col2\" class=\"data row1 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row1_col3\" class=\"data row1 col3\" >[0, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row1_col4\" class=\"data row1 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row1_col5\" class=\"data row1 col5\" >1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row2\" class=\"row_heading level0 row2\" >2</th>\n",
       "      <td id=\"T_9d3c2_row2_col0\" class=\"data row2 col0\" >0.664202</td>\n",
       "      <td id=\"T_9d3c2_row2_col1\" class=\"data row2 col1\" >[0, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row2_col2\" class=\"data row2 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row2_col3\" class=\"data row2 col3\" >[0, 1, 1]</td>\n",
       "      <td id=\"T_9d3c2_row2_col4\" class=\"data row2 col4\" >1</td>\n",
       "      <td id=\"T_9d3c2_row2_col5\" class=\"data row2 col5\" >0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row3\" class=\"row_heading level0 row3\" >3</th>\n",
       "      <td id=\"T_9d3c2_row3_col0\" class=\"data row3 col0\" >2.122685</td>\n",
       "      <td id=\"T_9d3c2_row3_col1\" class=\"data row3 col1\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row3_col2\" class=\"data row3 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row3_col3\" class=\"data row3 col3\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row3_col4\" class=\"data row3 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row3_col5\" class=\"data row3 col5\" >1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row4\" class=\"row_heading level0 row4\" >4</th>\n",
       "      <td id=\"T_9d3c2_row4_col0\" class=\"data row4 col0\" >0.544631</td>\n",
       "      <td id=\"T_9d3c2_row4_col1\" class=\"data row4 col1\" >[0, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row4_col2\" class=\"data row4 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row4_col3\" class=\"data row4 col3\" >[0, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row4_col4\" class=\"data row4 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row4_col5\" class=\"data row4 col5\" >0</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row5\" class=\"row_heading level0 row5\" >5</th>\n",
       "      <td id=\"T_9d3c2_row5_col0\" class=\"data row5 col0\" >1.728898</td>\n",
       "      <td id=\"T_9d3c2_row5_col1\" class=\"data row5 col1\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row5_col2\" class=\"data row5 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row5_col3\" class=\"data row5 col3\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row5_col4\" class=\"data row5 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row5_col5\" class=\"data row5 col5\" >1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row6\" class=\"row_heading level0 row6\" >6</th>\n",
       "      <td id=\"T_9d3c2_row6_col0\" class=\"data row6 col0\" >0.827317</td>\n",
       "      <td id=\"T_9d3c2_row6_col1\" class=\"data row6 col1\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row6_col2\" class=\"data row6 col2\" >0</td>\n",
       "      <td id=\"T_9d3c2_row6_col3\" class=\"data row6 col3\" >[1, 0, 0]</td>\n",
       "      <td id=\"T_9d3c2_row6_col4\" class=\"data row6 col4\" >0</td>\n",
       "      <td id=\"T_9d3c2_row6_col5\" class=\"data row6 col5\" >1</td>\n",
       "    </tr>\n",
       "    <tr>\n",
       "      <th id=\"T_9d3c2_level0_row7\" class=\"row_heading level0 row7\" >7</th>\n",
       "      <td id=\"T_9d3c2_row7_col0\" class=\"data row7 col0\" >2.644477</td>\n",
       "      <td id=\"T_9d3c2_row7_col1\" class=\"data row7 col1\" >[1, 1, 0]</td>\n",
       "      <td id=\"T_9d3c2_row7_col2\" class=\"data row7 col2\" >1</td>\n",
       "      <td id=\"T_9d3c2_row7_col3\" class=\"data row7 col3\" >[0, 1, 1]</td>\n",
       "      <td id=\"T_9d3c2_row7_col4\" class=\"data row7 col4\" >1</td>\n",
       "      <td id=\"T_9d3c2_row7_col5\" class=\"data row7 col5\" >1</td>\n",
       "    </tr>\n",
       "  </tbody>\n",
       "</table>\n"
      ],
      "text/plain": [
       "<pandas.io.formats.style.Styler at 0x7f2778ebbc70>"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "def highlight_diff(row):\n",
    "    \"\"\"Custom style function to highlight mismatched predictions.\"\"\"\n",
    "    return [\n",
    "        (\n",
    "            \"background-color: yellow\"\n",
    "            if row[\"Majority vote (Concrete ML)\"] != row[\"Majority vote (scikit-learn)\"]\n",
    "            else \"\"\n",
    "        )\n",
    "    ] * len(row)\n",
    "\n",
    "\n",
    "df = pd.DataFrame(\n",
    "    {\n",
    "        \"Distance\": distance[:, 0],\n",
    "        f\"Top{n_neighbors} (scikit-learn)\": [list(row) for row in topk_labels_sk],\n",
    "        \"Majority vote (scikit-learn)\": predict_sklearn,\n",
    "        f\"Top{n_neighbors} (Concrete ML)\": [list(row) for row in topk_labels_cml],\n",
    "        \"Majority vote (Concrete ML)\": pred_cml_simulate,\n",
    "        \"Ground truth\": y_test,\n",
    "    }\n",
    ")\n",
    "\n",
    "df.style.apply(highlight_diff, axis=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The difference in the top-k labels presented in the table above can be linked to two factors: the quantization of distances and the fact that the sorting algorithm is not stable."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Conclusion\n",
    "\n",
    "For real-world applications, especially those involving with large data-sets, the K-nearest neighbors classifier may face limitations due to its notable time and memory complexity.\n",
    "\n",
    "The K-nearest neighbors classifier matches its scikit-learn equivalent. The small difference in accuracy comes from quantization artifacts as well as the fact that the sorting algorithm is non-stable."
   ]
  }
 ],
 "metadata": {
  "execution": {
   "timeout": 10800
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
